package 我的Java学习_算法基础.day_07;

/**
 * @author 挚爱之夕
 * @date 2021/8/21 - 08 - 21 - 14:19
 * @Description: 我的暑假Java学习.day_07
 * @Version: 1.0
 */
public class _115_数独游戏 {
    public static void main(String[] args) {
        char[][] table = {
                {'0','0','5','3','0','0','0','0','0'},
                {'8','0','0','0','0','0','0','2','0'},
                {'0','7','0','0','1','0','5','0','0'},
                {'4','0','0','0','0','5','3','0','0'},
                {'0','1','0','0','7','0','0','0','6'},
                {'0','0','3','2','0','0','0','8','0'},
                {'0','6','0','5','0','0','0','0','9'},
                {'0','0','4','0','0','0','0','3','0'},
                {'0','0','0','0','0','9','7','0','0'}
        };
        dfs(table,0,0);
    }
    private static void dfs(char[][] table, int x, int y){
        if(x==9){
            print(table);
            System.exit(0);
        }
        if(table[x][y]=='0'){//虚位以待
            for(int k = 1;k<10;k++){    //k为1-9，将要填的数字
                if(check(table,x,y,k)){
                    table[x][y] = (char)('0'+k);
                    dfs(table,x+(y+1)/9,(y+1)%9);//处理下一个状态
                }
            }
            table[x][y] = '0';//回溯
        }else{
            dfs(table,x+(y+1)/9,(y+1)%9);//处理下一个状态
        }
    }
    private static void print(char[][] table){
        for (int i = 0; i < 9; i++) {
            System.out.println(new String(table[i]));
        }
    }
    private static boolean check(char[][] table,int i,int j,int k){
        //检查同行和同列
        for (int l = 0; l < 9; l++) {
            if(table[i][l]==(char)('0'+k)) return false;
            if(table[l][j]==(char)('0'+k)) return false;
        }
        //检查小九宫格
        for (int l = (i/3)*3; l <(i/3+1)*3 ; l++) {
            for(int m = (j/3)*3;m<(j/3+1)*3;m++){
                if(table[l][m]==(char)('0'+k)) return false;
            }
        }
        return true;
    }
}
